Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
Follow up:
Could you do get and put in O(1) time complexity?
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- At most
3 * 104calls will be made togetandput.
Average Rating: 3.87 (211 votes)
Solution
Approach 1: Ordered dictionary
Intuition
We're asked to implement the structure which provides the following operations in O(1) time :
-
Get the key / Check if the key exists
-
Put the key
-
Delete the first added key
The first two operations in O(1) time are provided by the standard hashmap, and the last one - by linked list.
There is a structure called ordered dictionary, it combines behind both hashmap and linked list. In Python this structure is called OrderedDict and in Java LinkedHashMap.
Let's use this structure here.
Implementation
Complexity Analysis
-
Time complexity : O(1) both for
putandgetsince all operations with ordered dictionary :get/in/set/move_to_end/popitem(get/containsKey/put/remove) are done in a constant time. -
Space complexity : O(capacity) since the space is used only for an ordered dictionary with at most
capacity + 1elements.
Approach 2: Hashmap + DoubleLinkedList
Intuition
This Java solution is an extended version of the the article published on the Discuss forum.
The problem can be solved with a hashmap
that keeps track of the keys and its values in the double linked list.
That results in O(1) time for put and get operations and
allows to remove the first added node in O(1) time as well.
One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.
One particularity about the double linked list implemented here
is that there are pseudo head and pseudo tail to mark the boundary,
so that we don't need to check the null node during the update.
Implementation
Complexity Analysis
-
Time complexity : O(1) both for
putandget. -
Space complexity : O(capacity) since the space is used only for a hashmap and double linked list with at most
capacity + 1elements.
June 26, 2019 6:37 AM
how come this question is downgraded as a medium question suddenly?
February 27, 2019 3:20 AM
Using an OrderedDict / LinkedHashMap to solve this problem in an interview setting is like using [::-1] / .reverse() to solve how to reverse a string, yeah you got it right but is that what the interviewer is looking for?
February 28, 2019 7:22 AM
I'd find a much better explanation and solution from the discussion section.
March 5, 2021 11:57 PM
@gchggy
Java version: https://leetcode.com/problems/lru-cache/discuss/45911/Java-Hashtable-%2B-Double-linked-list-(with-a-touch-of-pseudo-nodes)
Python version: https://leetcode.com/problems/lru-cache/discuss/45926/Python-Dict-%2B-Double-LinkedList
leetcode solution and discussions complement each other
July 10, 2020 10:24 AM
it would be nice if you posted a link to whatever you found better in the discuss section.
True, but in this case, someone copy pasted the same solution in discussion.
I really like the dummy head & tail technique. Much more simple implementation with those in place and really minimal extra memory overhead. I just spent an hour catching all the edge cases without them! I'm puzzled why my solution is slower than most - I presume most solutions are cheating and using an LinkedHashMap. I also suspect the performance numbers are based on unrealistically small sample sets.
Java Solution. Not a huge fan of the code proposed for solution #2. Here is a more straight forward code (same approach, just cleaner code).
class Node {
int value;
int key;
Node prev;
Node next;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
Node tail;
public DoublyLinkedList() {
head = new Node();
tail = new Node();
this.head.next = this.tail;
this.tail.prev = head;
}
public void insertHead(Node n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
}
public void remove(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
public int removeTail() {
Node n = tail.prev;
int key = n.key;
remove(n);
return key;
}
}
class LRUCache {
Map<Integer,Node> cache;
DoublyLinkedList list;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.list = new DoublyLinkedList();
}
public int get(int key) {
if (!cache.containsKey(key))
return -1;
update(key, cache.get(key));
return cache.get(key).value;
}
public void put(int key, int value) {
Node n = new Node(key, value);
if (cache.containsKey(key))
list.remove(cache.get(key));
else if (cache.size() >= capacity) {
int k = list.removeTail();
cache.remove(k);
}
list.insertHead(n);
cache.put(key, n);
}
private void update(int key, Node n) {
list.remove(n);
list.insertHead(n);
cache.put(key, n);
}
}
Last Edit: March 2, 2019 12:22 AM
@KingXun good question! The key in DLinkedNode would help us to remove the node itself from the cache at the moment the node becomes stale and is removed along with the invocation of the function popTail. We need to keep the key along with the node itself, because when the node is removed, we are not blessed with the key from the caller of LRU cache.
March 22, 2020 10:29 AM
tried everything I could, stack, de-que, priority queue, etc. I just never thought about using the f..king linked list! This drives me crazy.
April 3, 2021 11:33 AM
@wolfhound115 Can't delete a random node in deque except for the first or last. DLL can. That's why a vanilla Linked List won't work as well.
wait but a deque is effectively a doubly linked list right? (at least in the python implementation of it)
why remove oldest? what if a cache is frequently used and the eldest the same time?
September 28, 2019 10:36 AM
Does the interviewer really expects you to write this much code in just 30 mins?
I do not understand how this could possibly be implemented within 30 minutes without having prior knowledge of the question, especially if it is a whiteboard interview.
Can we assume a doubly linked list implementation is provided, implement only get and put, using assumed functions for doubly linked list? That would seem reasonable, otherwise the volume of this code just seems too much, even more so if you have to handle edge cases because you didn’t use dummy head and tail variables.
xxxxxxxxxx */class LRUCache {public: int size; list<int> lru; // MRU ... LRU unordered_map<int, list<int>::iterator> mp; // key -> iterator unordered_map<int, int> kv; // key -> value LRUCache(int capacity){ size = capacity; } int get(int key) { if (kv.count(key) == 0) return -1; updateLRU(key); return kv[key]; } void put(int key, int value) { if (kv.size() == size && kv.count(key) == 0) evict(); updateLRU(key); kv[key] = value; } void updateLRU(int key) { if (kv.count(key)) lru.erase(mp[key]); lru.push_front(key); mp[key] = lru.begin(); } void evict() { mp.erase(lru.back()); kv.erase(lru.back()); lru.pop_back(); }};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
